\section{Preliminaries}
\label{sec:TA_A}

%In this section, we will first present a CLP-based approach to compute the worst-case delays of the messages. CLP allows users to write constraints in logic programming and solves the problem using branch and bound search based on constraint programming. Computing the worst-case delays of messages on the FlexRay DYN segment is an NP-hard problem and hence, the CLP-based approach is computationally expensive and does not scale well. Hence, we will present an efficient heuristic.

	Our schedulability analysis technique relies on computing the worst-case response time of each message. If the worst-case response time of any message is greater than its deadline, we declare the given set of messages to be unschedulable; otherwise we report the worst-case response time.
	 
	Computing the worst-case response time of a message transmitted on the FlexRay bus consists of several components \cite{PPEPA08, ZengGN10}. For simplicity of exposition, we assume that $\messageDeadline_i\leq \messagePeriod_i$. However, this is not a restriction on our proposed method and in Section \ref{sec:busyPeriod}, we will discuss how our proposed algorithm can be extended to the case where $\messageDeadline_i>\messagePeriod_i$. Similarly, it is easy to accomodate jitter suffered by messages into our framework and this will be accounted for in Section \ref{sec:busyPeriod}.

The worst-case response time $\messageWCRT_i$ of a message $m_i$ consists of the following components.
\begin{equation}
\label{eq:msgWCRT}
\messageWCRT_i=\sigma_i+w_i+\messageLengthTime_i
\end{equation}
The first component $\sigma_i$ is the worst-case delay that a message can suffer during the first FlexRay cycle where the message $m_i$ is generated. To compute $\messageWCRT_i$, we are interested in the scenario where $\sigma_i$ is maximum. Let the set of high priority messages be denoted as $hp(m_i) = \{m_1, m_2, \cdots, m_N \}$. Now the worst-case, scenario occurs if $m_i$ arrives just after the corresponding minislot starts and no higher priority message  $hp(m_i)$, was transmitted in this FlexRay cycle. The value of $\sigma_i$ can be computed as follows:
\begin{equation}
\sigma_i = \flexrayCycleLength - (\flexraySTLength+(ID_i-1)\minislotLength)
\end{equation}  
Note here that $\sigma_i$ can be computed with the straightforward algebraic equation from the system model.

The second component, $w_i$ is essentially the delay caused to $m_i$ by the higher priority messages. $w_i$ is the summation of two terms:
\begin{equation}
\label{eq:busCycle}
w_i=busCycles_i+lastCycle_i
\end{equation}
In the above equation, $busCycles_i$ is the total number of cycles message $m_i$ has to wait due to interference by higher priority messages and $lastCycle_i$ is the time interval from the start of the last cycle to the beginning of the transmission in that cycle. The value of $lastCycle_i$ can be bounded by considering the last possible moment when $m_i$ can be sent in the FlexRay cycle which is defined by the value of $pLatestTx$. $pLatestTx$ is specified as a part of the FlexRay configuration in the system model. The computation of $busCycles_i$ will be detailed in the following section. %A set of high priority messages $hp(m_i) = \{m_1, m_2, \cdots, m_N \}$. 
Let us denote the minimum amount of communication $\phi_{m_i}$ (in minislots) that needs to exists in a cycle $l$ such that the message $m_i$ is delayed into the next cycle $l + 1$. $\phi_{m_i}$ can be computed based on the value of $pLatestTx$. For instance, if $pLatestTx$ is equal to $\numberOfMinislots$, then $\phi_{m_i}$ can be computed as follows.
	\begin{equation}
		\phi_{m_i} = \numberOfMinislots + 2 - \left(W_{m_i} + ID_{m_i} \right)
	\end{equation}
	%Note that the value of $\phi_{m_i}$ depends only on the values of $m_a$'s parameters and the total number of available minislots.
	

The last component $\messageLengthTime_i$ of $\messageWCRT_i$, as shown in Equation~\ref{eq:msgWCRT}, is the time needed by the message to be transmitted completed when, finally,  it gains access to the bus and this can be computed as $\messageLengthTime_i=\minislotLength \times \messageSize_i$. 

